//232 Implement Queue using Stacks
/*
尝试使用栈（stack）来实现队列

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

可以用两个栈来实现一个队列：因为我们需要得到先入先出的结果，所以必定要通过一
个额外栈翻转一次数组。这个翻转过程既可以在插入时完成，也可以在取值时完成
*/
class MyQueue
{
	stack<int> in, out;

public:
	MyQueue() {}
	void push(int x)
	{
		in.push(x);
	}
	int pop()
	{
		in2out();
		int x = out.top();
		out.pop();
		return x;
	}
	int peek()
	{
		in2out();
		return out.top();
	}
	void in2out()
	{
		if (out.empty())
		{
			while (!in.empty())
			{
				int x = in.top();
				in.pop();
				out.push(x);
			}
		}
	}
	bool empty()
	{
		return in.empty() && out.empty();
	}
};
